//
// Created by wenyaxi on 24-10-30.
//

#include <common.h>


class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        priority_queue<ListNode *, vector<ListNode *>, std::function<bool(ListNode *, ListNode *)> > pq(
            [](ListNode *l, ListNode *r) {
                return l->val > r->val;
            });

        for (auto list: lists) {
            if (list) {
                pq.push(list);
            }
        }
        ListNode *dummy = new ListNode(0);
        ListNode *cur = dummy;
        while(!pq.empty()) {
            auto top = pq.top();
            pq.pop();
            if (top->next) {
                pq.push(top->next);
            }
            cur->next = top;
            cur = cur->next;
        }
        return dummy->next;
    }
};

int main(int argc, char *argv[]) {
    //[[1,4,5],[1,3,4],[2,6]]
    Solution s;
    auto n1 = ListNode::of({1, 1,2});
    auto n2 = ListNode::of({1, 1,2});
    vector<ListNode *> lists;
    lists.push_back(n1);
    lists.push_back(n2);
    auto res = s.mergeKLists(lists);
    cout << *res << endl;
    return 0;
}
